// 快速排序
export function quickSort(arr, left, right) {
    if (left < right) {
        let pos = partition(arr, left, right)
        quickSort(arr, left, pos - 1)
        quickSort(arr, pos + 1, right)
        return arr
    } else {
        return arr
    }
}

function partition(arr, left, right) {
    let pivotPos = left
    let pivot = arr[left]
    for (let i = left + 1; i <= right; i++) {
        if (arr[i] < pivot) {
            pivotPos++
            if (pivotPos != i) {
                let t = arr[pivotPos]
                arr[pivotPos] = arr[i]
                arr[i] = t
            }
        }
    }
    arr[left] = arr[pivotPos]
    arr[pivotPos] = pivot
    return pivotPos
}